Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science
Identifieur interne : 000556 ( Main/Exploration ); précédent : 000555; suivant : 000557Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science
Auteurs : Akio Fujiyoshi [Japon] ; Masakazu Suzuki (mathématicien) [Japon]Source :
- IEICE transactions on information and systems [ 0916-8532 ] ; 2011.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000144
- to stream PascalFrancis, to step Curation: 000629
- to stream PascalFrancis, to step Checkpoint: 000110
- to stream Main, to step Merge: 000562
- to stream Main, to step Curation: 000556
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science</title><author><name sortKey="Fujiyoshi, Akio" sort="Fujiyoshi, Akio" uniqKey="Fujiyoshi A" first="Akio" last="Fujiyoshi">Akio Fujiyoshi</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Computer and Information Sciences, Ibaraki University</s1><s2>Hitachi-shi, 316-8511</s2><s3>JPN</s3><sZ>1 aut.</sZ></inist:fA14><country>Japon</country><wicri:noRegion>Hitachi-shi, 316-8511</wicri:noRegion></affiliation></author><author><name sortKey="Suzuki, Masakazu" sort="Suzuki, Masakazu" uniqKey="Suzuki M" first="Masakazu" last="Suzuki">Masakazu Suzuki (mathématicien)</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>Graduate School of Mathematics, Kyushu University</s1><s2>Fukuoka-shi, 819-0395</s2><s3>JPN</s3><sZ>2 aut.</sZ></inist:fA14><country>Japon</country><placeName><settlement type="city">Fukuoka</settlement><region type="province">Kyūshū</region><region type="prefecture">Préfecture de Fukuoka</region></placeName><orgName type="university">Université de Kyūshū</orgName><placeName><settlement type="city">Fukuoka</settlement><region type="province">Kyūshū</region><region type="prefecture">Préfecture de Fukuoka</region></placeName><orgName type="university" n="3">Université de Kyūshū</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">11-0220366</idno><date when="2011">2011</date><idno type="stanalyst">PASCAL 11-0220366 INIST</idno><idno type="RBID">Pascal:11-0220366</idno><idno type="wicri:Area/PascalFrancis/Corpus">000144</idno><idno type="wicri:Area/PascalFrancis/Curation">000629</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000110</idno><idno type="wicri:doubleKey">0916-8532:2011:Fujiyoshi A:minimum:spanning:tree</idno><idno type="wicri:Area/Main/Merge">000562</idno><idno type="wicri:Area/Main/Curation">000556</idno><idno type="wicri:Area/Main/Exploration">000556</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science</title><author><name sortKey="Fujiyoshi, Akio" sort="Fujiyoshi, Akio" uniqKey="Fujiyoshi A" first="Akio" last="Fujiyoshi">Akio Fujiyoshi</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Computer and Information Sciences, Ibaraki University</s1><s2>Hitachi-shi, 316-8511</s2><s3>JPN</s3><sZ>1 aut.</sZ></inist:fA14><country>Japon</country><wicri:noRegion>Hitachi-shi, 316-8511</wicri:noRegion></affiliation></author><author><name sortKey="Suzuki, Masakazu" sort="Suzuki, Masakazu" uniqKey="Suzuki M" first="Masakazu" last="Suzuki">Masakazu Suzuki (mathématicien)</name><affiliation wicri:level="4"><inist:fA14 i1="02"><s1>Graduate School of Mathematics, Kyushu University</s1><s2>Fukuoka-shi, 819-0395</s2><s3>JPN</s3><sZ>2 aut.</sZ></inist:fA14><country>Japon</country><placeName><settlement type="city">Fukuoka</settlement><region type="province">Kyūshū</region><region type="prefecture">Préfecture de Fukuoka</region></placeName><orgName type="university">Université de Kyūshū</orgName><placeName><settlement type="city">Fukuoka</settlement><region type="province">Kyūshū</region><region type="prefecture">Préfecture de Fukuoka</region></placeName><orgName type="university" n="3">Université de Kyūshū</orgName></affiliation></author></analytic><series><title level="j" type="main">IEICE transactions on information and systems</title><title level="j" type="abbreviated">IEICE trans. inf. syst.</title><idno type="ISSN">0916-8532</idno><imprint><date when="2011">2011</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">IEICE transactions on information and systems</title><title level="j" type="abbreviated">IEICE trans. inf. syst.</title><idno type="ISSN">0916-8532</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Labelled graph</term><term>Minimum spanning tree MST</term><term>NP hard problem</term><term>Optical character recognition</term><term>Pattern recognition</term><term>Series parallel connection</term><term>Time series</term><term>Tree(graph)</term><term>Vertex(graph)</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Arbre recouvrant minimal</term><term>Sommet graphe</term><term>Graphe marqué</term><term>Reconnaissance optique caractère</term><term>Problème NP difficile</term><term>Arbre graphe</term><term>Série temporelle</term><term>Algorithme</term><term>Montage série parallèle</term><term>Reconnaissance forme</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.</div></front></TEI><affiliations><list><country><li>Japon</li></country><region><li>Kyūshū</li><li>Préfecture de Fukuoka</li></region><settlement><li>Fukuoka</li></settlement><orgName><li>Université de Kyūshū</li></orgName></list><tree><country name="Japon"><noRegion><name sortKey="Fujiyoshi, Akio" sort="Fujiyoshi, Akio" uniqKey="Fujiyoshi A" first="Akio" last="Fujiyoshi">Akio Fujiyoshi</name></noRegion><name sortKey="Suzuki, Masakazu" sort="Suzuki, Masakazu" uniqKey="Suzuki M" first="Masakazu" last="Suzuki">Masakazu Suzuki (mathématicien)</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000556 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000556 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:11-0220366
|texte= Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science
}}
| This area was generated with Dilib version V0.6.32. |  |